package final2107.day02;

public class BinarySearchTree<E extends Comparable<E>> {
    //定义根节点
    private Node root;

    //定义add(E) 添加元素，返回值为boolean类型
    public boolean add(E e){
        //判断root是否为null
        if (root==null) {
            root = new Node(e);
            return true;
        }
        //root不为null，尝试将新节点添加到root的left/right
        return root.append(e);
    }

    //根据元素查找对应的节点
    public Node get(E e){
        //判断树是否为null
        if (root==null)
            return null;
        //树不为null，从root开始查找目标节点
        return root.isDest(e);
    }

    @Override
    public String toString() {
        //判断root是否为null，为null，返回[]，结束
        if (root==null)
            return "[]";
        //创建StirngBUilder对象
        StringBuilder builder = new StringBuilder("[");
        //调用midOrder()得到StringBuilder
        builder = root.midOrder(builder);
        //处理StringBuilder，返回String
//        builder.setCharAt(builder.length()-1,']');
        builder.deleteCharAt(builder.length()-1).append("]");
        return builder.toString();
    }

    //定义内部类来表示二叉排序树中的节点对象
    private class Node{
        private E data;
        private Node left;
        private Node right;

        Node(E ele){
            this.data = ele;
        }

        //尝试向节点上添加新元素
        public boolean append(E e) {
            //判断新元素是否和当前节点的元素相等，若相等，添加失败
            if (e.compareTo(data)==0)
                return false;
            //大于，向右子树添加
            else if (e.compareTo(data)>0){
                if (right==null){
                    right = new Node(e);
                    return true;
                }
                //right不为null，
                return right.append(e);
            }else {
                //e小于data，添加为左子树
                if (left==null){
                    left = new Node(e);
                    return true;
                }
                return left.append(e);
            }
        }

        //中序遍历 - 左根右
        public StringBuilder midOrder(StringBuilder builder){
            //遍历left
            if (left!=null)
                left.midOrder(builder);
            //获取gen
            builder.append(data).append(",");
            //遍历right
            if (right!=null)
                right.midOrder(builder);
            return builder;
        }

        //判断某个目标节点是否为目标元素对应的对象
        public Node isDest(E e) {
            //判断是否相等
            if (e.compareTo(data)==0)
                return this;
            //若不相等，判断大于还是小于
            else if (e.compareTo(data)>0){
                //e大于节点的元素的，到其右子树上继续查找
                if (right==null)
                    return null;
                return right.isDest(e);
            }else {  //e小于节点的元素
                if (left==null)
                    return null;
                return left.isDest(e);
            }
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
}

